/*
https://leetcode.cn/problems/meChtZ/solution/suan-fa-xiao-ai-li-kou-bei-li-jie-zhen-t-tg1z/
 */
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class SolutionLCP20 {
    public int busRapidTransit(int target, int inc, int dec, int[] jump, int[] cost) {
        Queue<Integer> queue=new LinkedList<>();
        queue.offer(target);
        Map<Integer,Long> map=new HashMap<>();
        map.put(target,0L);
        long ans=Long.MAX_VALUE;
        while(!queue.isEmpty()){
            int t=queue.poll();
            if (map.get(t)>=ans){
                continue;
            }
            ans=Math.min(ans,map.get(t)+(long)t*inc);
            if (t<=1){
                continue;
            }
            for (int i=0;i<jump.length;i++) {
                if (t%jump[i]==0){
                    if (!map.containsKey(t/jump[i]) || map.get(t/jump[i])>map.get(t)+cost[i]) {
                        queue.offer(t/jump[i]);
                        map.put(t/jump[i],map.get(t)+cost[i]);
                    }
                }else {
                    int p=t%jump[i];
                    if (t/jump[i]!=0 && (!map.containsKey(t/jump[i]) || map.get(t/jump[i])>map.get(t)+cost[i]+(long)p*inc)){
                        queue.offer(t/jump[i]);
                        map.put(t/jump[i],map.get(t)+cost[i]+(long)p*inc);
                    }
                    if (!map.containsKey(t/jump[i]+1) || map.get(t/jump[i]+1)>map.get(t)+cost[i]+(long)(jump[i]-p)*dec){
                        queue.offer(t/jump[i]+1);
                        map.put(t/jump[i]+1,map.get(t)+cost[i]+(long)(jump[i]-p)*dec);
                    }
                }
            }
        }
        return (int)(ans%1000000007);
    }

    public static void main(String[] args) {
        System.out.println(new SolutionLCP20().busRapidTransit(954116209,725988,636911,new int[]{524425,158389},new int[]{41881,941330}));
    }
}
